An Initial Seed Selection Algorithm for K-means Clustering of Georeferenced Data to Improve Replicability of Cluster Assignments for Mapping Application

摘要

K-means is one of the most widely used clustering algorithms in variousdisciplines, especially for large datasets. However the method is known to behighly sensitive to initial seed selection of cluster centers. K-means++ hasbeen proposed to overcome this problem and has been shown to have betteraccuracy and computational efficiency than k-means. In many clustering problemsthough -such as when classifying georeferenced data for mapping applications-standardization of clustering methodology, specifically, the ability to arriveat the same cluster assignment for every run of the method i.e. replicabilityof the methodology, may be of greater significance than any perceived measureof accuracy, especially when the solution is known to be non-unique, as in thecase of k-means clustering. Here we propose a simple initial seed selectionalgorithm for k-means clustering along one attribute that draws initial clusterboundaries along the 'deepest valleys' or greatest gaps in dataset. Thus, itincorporates a measure to maximize distance between consecutive cluster centerswhich augments the conventional k-means optimization for minimum distancebetween cluster center and cluster members. Unlike existing initializationmethods, no additional parameters or degrees of freedom are introduced to theclustering algorithm. This improves the replicability of cluster assignments byas much as 100% over k-means and k-means++, virtually reducing the varianceover different runs to zero, without introducing any additional parameters tothe clustering process. Further, the proposed method is more computationallyefficient than k-means++ and in some cases, more accurate.